package test;

import java.util.Arrays;

/**
 * 描述：
 *      下一个排列
 *      从末尾开始找，找到第一个nums[j] > nums[j - 1]的位置，j-1的位置就是需要被交换的位置，
 *      与它交换的是j~nums.length位置上第一个大于nums[j - 1]的数
 * @author hl
 * @version 1.0
 * @date 2020/11/12 17:24
 */
public class NextPermutation {
    public void nextPermutation(int[] nums) {
        int min = nums.length - 1;
        int j = nums.length - 1;
        //从末尾开始找，找到第一个nums[j] > nums[j - 1]的位置，j-1的位置就是需要被交换的位置
        while(j > 0 && nums[j] <= nums[j - 1]){
            min = nums[min] > nums[j] ? j : min;
            j--;
        }
        //在j~nums.lenght的区间中进行升序排列
        for(int i = j + 1; i < nums.length; i++){
            for(int k = i - 1; k >= j && nums[k] > nums[k + 1]; k--){
                int temp = nums[k];
                nums[k] = nums[k + 1];
                nums[k + 1] = temp;
            }
        }
        //交换j - 1和第一个大于j - 1的位置
        if(j != 0){
            for(int i = j; i < nums.length; i++){
                if(nums[i] > nums[j - 1]){
                    int temp = nums[j - 1];
                    nums[j - 1] = nums[i];
                    nums[i] = temp;
                    break;
                }
            }

        }

    }
}
